package 数据结构OJ;

import java.util.*;

/**
 * @author shy_black
 * @date 2019/6/26 10:30
 * @Description:
 * 约瑟夫环问题：使用链表的思想，直接调用jdk的linkedlist实现，
 * 当链表中剩下的小孩大于一个的时候，就进行数数字环节，数数字的过程可以看做对剩下的学生做取余，
 * 从当前学生开始数数可以看做从删除学生开始进行取余，只要将删除的节点缓存起来即可
 *
 */
public class 孩子们的游戏_圆圈中最后剩下的数 {


    public int LastRemaining_Solution(int n, int m) {
        //n个小朋友，数m次，是一个闭环
        //得出谁是最后一个
        LinkedList<Integer> list = new LinkedList();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int tmp = 0;
        while (list.size() > 1) {
            //1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
            //m = 5 tmp初始为0
            //1 2 3 4 5 5退出
            //1 2 3 4 6 7 8 9 10 10退出
            //1 2 3 4 5 6 7 8 9 11 12 13 14 15 15quit
            //1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 20quit
            //共有20个小朋友，数11次
            //11%20
            tmp = (tmp + m - 1) % list.size();
            list.remove(tmp);
        }
        return list.size() == 1 ? list.get(0) : -1;
    }
}